package com.yeung.dynamicplan;

/**
 * 以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。
 */
public class 最长公共子序列 {
    public static void main(String[] args) {
        int[] s1 = {1, 3, 4, 5, 6, 7, 7, 8}, s2 = {3, 5, 7, 4, 8, 6, 7, 8, 2};

        int l1 = s1.length;
        int l2 = s2.length;
        int dp[][] = new int[l1][l2];


        for (int i = 0; i < l1; i++)
            for (int j = 0; j < l2; j++) {
                if (i == 0 || j == 0) dp[i][j] = 0;
                else if (s1[i - 1] == s2[j - 1])
                    // LCS(Ax, By) = LCS(x - 1, y - 1) + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    // 如果t  ≠ Ax，则有L(x, y)= L(x - 1, y)，因为根本没Ax的事嘛。
                    //LCS(x,y) = LCS(x – 1, y)
                    //如果t  ≠ By,l类似L(x, y)= L(x , y - 1)
                    //          LCS(x,y) = LCS(x, y – 1)
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);

            }
        System.out.println(dp[l1 - 1][l2 - 1]);

    }
}
